1. Field of the Invention
The invention relates to a method of halftoning grey values of pixels obtained by a photoelectric scanning of an image. The invention also relates to an image reproduction apparatus for reproducing grey value signals of an image produced by photoelectric scanning.
2. Description of Related Art
If an image is scanned photoelectrically, e.g. by a CCD scanner, grey values are obtained which correspond to surface coverages of different image elements of an image, i.e. pixels. The number of different grey values possible in such cases is determined by the characteristics of the CCD scanner and the extent of its dynamic range. If an analogue grey value generated by a CCD scanner is represented, for example, by a digital 8-bit code, then 256 possible different grey values are possible. If such grey value information is reproduced by image reproduction devices such as, for example, electrophotographic printers or inkjet printers, this grey value information must be converted into the degrees of coverage to be reproduced by such apparatus. Generally, only two possible degrees of coverage have to be reproduced, with toner powder in the case of electrophotography, or with ink in the case of an inkjet printer, these two possible degrees being white or black depending on the presence or absence of toner powder or ink. The multivalent grey values then have to be converted to not more than two grey values corresponding to white or black. If the ratio of the number of white and black pixels over a specific area is determined by the original grey value, an impression of the original grey value can be approximated. This method of reproducing grey values by way of a limited number of degrees of coverage is designated halftoning.
Generally, halftoning methods can be classified either under the designation of dithering or the designation of error diffusion. In the case of dithering, the pixels are divided up into contiguous groups of fixed dimensions, known as dither matrices, by which the grey value impression is approximated as well as possible for each group. Dithering has the disadvantage of reduced reproduction of detailed image information since the resolution is determined by the dimensions of the dither matrix.
Error diffusion does not have this disadvantage, since in this case the process is carried out for each pixel. A grey value for a pixel is rounded off to a bivalent binary value by thresholding, such value representing a minimum or a maximum surface coverage, the quantisation error which occurs in these circumstances being distributed over grey values of a number of neighbouring pixels yet to be thresholded. By distributing or diffusing the quantisation error over the immediate vicinity of the pixel, an approximation of the original grey value is finally obtained over a larger number of pixels. Chapter 8 of "Digital Halftoning" by Ulichney, Robert, MIT Press, 1987, describes a number of error diffusion methods. One known distribution of the quantisation error over neighbouring pixels is known as Floyd and Steinberg. In this case, the quantisation error is distributed over four neighbouring pixels in accordance with a fixed distribution code.
However, despite the fact that error diffusion is a pixel processing operation, a sharp edge transition may be reproduced fuzzily in an image as a result of the distribution of the quantisation error over a number of pixels. The prior art describes a number of devices in which error diffusion is applied at edge transitions.
For example, U.S. Pat. No. 4,876,610 describes an image reproduction apparatus using error diffusion, in which distribution of the quantisation error outside edge transitions in the image takes place over 12 neighbouring pixels in accordance with the Jarvis and Judice distribution, while at edge transitions it takes place over four adjacent pixels in accordance with the Floyd and Steinberg distribution. Edge transitions are determined by filtering the image signals through a two-dimensional Laplace filter followed by thresholding. Although restricting the diffusion area at edge transitions gives an improved reproduction thereof, fuzziness is still possible.
U.S. Pat. No. 4,878,125 also applies the distribution of the quantisation error over 12 pixels in the case of an edge transition. This is done to the extent that the distribution of the quantisation error in non-edge areas is effected uniformly with substantially identical weighting factors while at edge zones it is effected with a high concentration with a considerable difference in weighting factors. Edge transitions are detected either by a two-dimensional Laplace filter or by a detection of minimum and maximum grey values in a block of pixels. Nevertheless, fuzziness of an edge can always occur locally.
Another disadvantage of the apparatus described in the said patents is the complex character thereof. In both cases, two different sets of weighting coefficients are required for the distribution of the quantisation error as well as the necessary buffers and circuits for the edge transition detection. In addition, multiplying the quantisation error with different weighting coefficients also necessitates the required capacity.
U.S. Pat. No. 5,140,432 even uses a number of sets of different weighting distributions which differ from one another in diffusion length, in variation of the magnitude of the weighting factors, and in the direction of the diffusion. In addition, it is not only the presence of an edge transition that is detected, but also its direction and slope. This determination is based on grey values of a large number of pixels. A gradient is determined for a number of sub-superpixels of a size of 3.times.3 pixels. A profile of an edge transition is then determined over a superpixel which in turn contains 4.times.5 such sub-superpixels. A "profile comparator" is used to select a specific set of weighting coefficients. A set is selected which fits the profile found. This implies that the direction of the diffusion takes place primarily in the direction of the gradient of the edge transition. The size of the diffusion area is also inversely proportional to the size of this gradient.
The complexity of this apparatus is self-evident. A large number of pixels with associated processing operations are still involved in the detection of an edge transition and diffusion of the quantisation error.
Apart from their complexity, the said apparatus in the above patents are characterised by adaptation of the diffusion area at an edge transition to a less large area than is the case in areas without edge transitions. An apparatus which carries out no diffusion at all at edge transitions is known from WPT Patent Application 9106174. However, this has the disadvantage of reduced reproduction of the grey value of an edge transition.
Chapter 8.3.1 of the above-mentioned "Digital Halftoning" by Ulichney describes a very simple embodiment of error diffusion in which the quantisation error is distributed over only one pixel. In this case there is accordingly no necessity for multiplication of a quantisation error in accordance with a specific weighting factor. As already indicated hereinbefore, however, this gives rise to the incidence of line-like tracks of identical pixel values in the halftoned image. A solution is offered to counteract the formation of these regular tracks. This consists of a random choice of a pixel over which the quantisation error is diffused. As described hereinbefore, the addition of a random component to the weighting factors in the case of error diffusion over several pixels is a suitable method of counteracting the incidence of regular structures in such an embodiment. A disadvantage, however, is that a random generator also contributes to the complexity. In addition, a random choice at edge transitions of a pixel over which the quantisation area is distributed or a random choice of that part of the quantisation error that is to be distributed over a specific pixel in turn again gives rise to fuzzy edge transitions.